//
// Description: 238. 除自身以外数组的乘积
// Created by Loading on 2022/5/2.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> productExceptSelf(vector<int> &nums) {
    int n = nums.size();
    // 先将 answer 构造为前缀乘积，answer[i] 为 i 左侧所有元素乘积（不包括 i 位置）
    vector<int> answer(n);
    answer[0] = 1;
    for (int i = 1; i < n; ++i) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }

    // 使用一个变量从右侧迭代
    int R = 1;
    for (int i = n - 1; i >= 0; --i) {
        // 更新 answer
        answer[i] *= R;
        // 迭代器更新，依次乘右侧元素
        R *= nums[i];
    }

    return answer;
}

int main() {
    vector<int> nums{-1, 1, 0, -3, 3};
    auto res = productExceptSelf(nums);
    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}